package com.zhanghp.class027;

import com.zhanghp.common.ListNode;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 合并K个有序链表
 * 测试链接：https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
 *
 * @author zhanghp
 * @since 2024/3/28 13:42
 */
public class Code01_MergeKSortedLists {

    // O(nlogk)
    public static ListNode mergeKLists(ArrayList<ListNode> arr){

        PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        if (arr.size() == 0) {
            return null;
        }
        for (int i = 0; i < arr.size(); i++) {
            ListNode listNode = arr.get(i);
            if ( listNode != null) {
                queue.offer(listNode);
            }
        }
        if (queue.isEmpty()) {
            return null;
        }
        ListNode pre = queue.poll();
        ListNode ans = pre;
        if (ans.next != null) {
            queue.offer(ans.next);
        }
        while (!queue.isEmpty()) {
            ListNode cur = queue.poll();
            ans.next = cur;
            ans = cur;
            if (cur.next != null) {
                queue.offer(cur.next);
            }
        }
        return pre;
    }

}
